#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int base = 1<<15;
const int mbase = base - 1;
const int N = 5e4+10;

int p[40],pcnt,c,m,n,mn[N<<2],P;
ll c0[40][base],c1[40][base],a[N][40],val[N<<2];

ll Mo(ll x,int mod){return x > mod ? x % mod + mod : x;}

int getphi(int x){
	int res = x;
	for(int i = 2;i * i <= x;i++){
		if(x % i == 0) res = res / i * (i-1);
		while(x % i == 0) x = x / i;
	}if(x > 1) res = res / x * (x - 1);
	return res;
}

//ll qp(ll x,int t){ll res=1;for(;t;t>>=1,x = Mo(x*x)) if(t&1)res=Mo(res*x);return res;}

void init(){
	for(int i = 0;i <= pcnt;i++){
		c0[i][0] = c1[i][0] = 1;
		for(int j = 1;j < base;j++) c0[i][j] = Mo(c0[i][j-1] * c , p[i]);
		c1[i][1] = Mo(c0[i][mbase]*c,p[i]);
		for(int j = 2;j < base;j++) c1[i][j] = Mo(c1[i][j-1] * c1[i][1] , p[i]);
	}
}

ll Lp(ll x,int t){return Mo(c0[x][t&mbase] * c1[x][t>>15],p[x]);}

ll calc(int x,int cnt,int t){
	if(!cnt) return Mo(x,p[t]); if(t == pcnt) return c ? 1 : 0;
	return Lp(t,calc(x,cnt-1,t+1));
}

void pushup(int o){
	mn[o] = min(mn[o<<1],mn[o<<1|1]);
	val[o] = (val[o<<1] + val[o<<1|1]) % P;
}

void build(int o = 1,int l = 1,int r = n){
	if(l == r) return val[o] = a[l][0],mn[o] = 0,void(); int mid = l+r>>1;
	build(o<<1,l,mid); build(o<<1|1,mid+1,r); pushup(o);
}

void upd(int xl,int xr,int o = 1,int l = 1,int r = n){
	if(mn[o] > pcnt) return;
	if(l == r) return mn[o]++,val[o] = a[l][mn[o]],void();
	int mid = l+r>>1; if(xr <= mid) upd(xl,xr,o<<1,l,mid);else if(xl > mid) upd(xl,xr,o<<1|1,mid+1,r);
	else upd(xl,mid,o<<1,l,mid),upd(mid+1,xr,o<<1|1,mid+1,r); pushup(o);
}

ll query(int xl,int xr,int o = 1,int l = 1,int r = n){
	if(xl == l && xr == r) return val[o];
	int mid = l+r>>1; if(xr <= mid) return query(xl,xr,o<<1,l,mid);else if(xl > mid) return query(xl,xr,o<<1|1,mid+1,r);
	else return (query(xl,mid,o<<1,l,mid) + query(mid+1,xr,o<<1|1,mid+1,r)) % P;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in,P = in,c = in;
	p[pcnt] = P; while(p[pcnt] > 1) ++pcnt,p[pcnt] = getphi(p[pcnt-1]);
	init();
	for(int i = 1;i <= n;i++) {
		a[i][0] = in;
		for(int j = 1;j <= pcnt+1;j++) a[i][j] = calc(a[i][0],j,0) % P;
	}
	build();
	while(m--){
		int op = in,l = in,r = in;
		if(op == 0) upd(l,r);
		else printf("%lld\n",query(l,r));
	}
	return 0;
}

